package LinkedList;

import Node.ListNode;

/**
 * 删除排序链表中重复的元素，推荐的通用解法，运行链表分解的技巧
 */
public class DuplicateRemoval {

    /**
     * 解法一：通用链表分解方式
     *
     * @param head
     * @return
     */
    public ListNode generalLinkedListDecomposition(ListNode head) {
        // 将原链表拆分为两条链表
        // 一条链表存放不重复的节点，另一条链表存放不重复的的节点
        // 运用虚拟头结点的技巧，题目说了 node.val <= 100, 所以用 101 做虚拟头节点
        ListNode dummyUnique = new ListNode(101);
        ListNode dummyDup = new ListNode(101);

        ListNode pUniq = dummyUnique, pDup = dummyDup;
        ListNode p = head;

        while (p != null) {
            // 链表有重复值
            if ((p.next != null && p.val == p.next.val) || p.val == pDup.val) {
                // 发现重复值，链接到重复链表的后面
                pDup.next = p;
                pDup = pDup.next;
            } else {
                // 不是重复链表，接到不重复链表的后面
                pUniq.next = p;
                pUniq = pUniq.next;
            }

            p = p.next;
            // 将原链表和新链表断开
            pUniq.next = null;
            pDup.next = null;
        }
        return dummyUnique.next;
    }

    /**
     * 快慢指针解法
     *
     * @param head
     * @return
     */
    public ListNode fastSlowPointer(ListNode head) {

        ListNode dummy = new ListNode(-1);
        ListNode p = dummy, q = head;
        while (q != null) {
            if (q.next != null && q.val == q.next.val) {
                // 发现重复节点，跳过这些节点
                while (q.next != null && q.val == q.next.val)
                    q = q.next;
                q = q.next;
                // 此时 q 跳过了这一段重复节点
                if (q == null)
                    q.next = null;
                // 不过下段元素也可能重复，等下次while循环判断
            } else {
                // 不是重复节点，接到dummy节点的后面
                p.next = q;
                p = p.next;
                q = q.next;
            }
        }
        return dummy.next;
    }

    /**
     * 递归解法
     * @param head
     * @return
     */
    public ListNode recursion(ListNode head) {
        // base case
        if (head == null || head.next == null)
            return null;
        if (head.val != head.next.val) {
            // 如果头结点和身后节点的值不同，则对之后的链表去重即可
            head.next = recursion(head.next);
            return head;
        }
        // 如果头结点和身后节点的值相同，则说明从 head 开始存在若干重复节点
        // 越过重复节点，找到 head 之后那个不重复的节点
        while (head.next != null && head.val == head.next.val) {
            head = head.next;
        }
        // 直接返回那个不重复节点开头的链表的去重结果，就把重复节点删掉了
        return recursion(head.next);
    }
}
